This invention relates in general to binary addition, and in specific to encoding the carry in for each bit of the operands in an addition calculation.
Binary addition is similar to numerical addition. The most basic form of binary addition entails starting with the least significant digit, and adding the two numbers, and moving a carry, if any, into the next significant digit addition. For example, consider the addition of the bit stream 010 and a bit stream 111. The addition of the least significant bits is 0+1, with a sum of 1, and a carry out of 0. The addition of the next significant bits are 1+1 plus a carry in of 0, with a sum of 0, and a carry out 1. The addition of the next significant bits are 0+1 plus a carry in of 1, with a sum of 0, and a carry out 1. Thus, the addition yields 001 plus a carry out of 1, or 1001.
The sequential addition described above works well for small bit streams, e.g. 3 bits, but becomes inefficient for large bit streams, e.g. 64 bits. Thus, the prior art uses carry select addition, which is similar to sequential addition, but breaks the bit streams into smaller blocks and performs two calculations, a first assuming that the carry bit is a zero, the second assumes the carry bit is a one. For example, consider a bit stream of 100101 which is added to bit stream 110001, this would yield 1010110 using sequential addition. With carry select addition these streams would be split into blocks 100 and 101 and 110 and 001, respectively. The addition of the blocks are 101+001 and 100+110. Now 100+110 would be calculated in two ways, the first assumes a carry in of 0 and the second assumes a carry in of 1. Thus, 100 +110+0=1010, and 100+110+1=1011. The addition of 101+001=110 with a carry out of 0, thus the carry in of 0 calculation for the 100+110 addition should be used. The two calculations are then concatenated together to form (1010) (110)=1010110. Note that the additions of the two segments can be performed in parallel. Further note that a 2 to 1 multiplexer (MUX) is typically used to select between the carry 0 and carry 1 calculations.
The only difference between the carry in of 0 calculation and the carry in of 1 calculation is in the carry in to each bit. Hence, two signals are used to encode the conditional carry in to each bit in the block; C0 is the carry in to a bit for carry in to the block of zero, and C1 is the carry in to the bit for carry in to this block of one. In a dual-rail domino implementation, the C0 and C1 inputs become four signals to represent each bit in the segment: C0H, C0L, and C1H, C1L. Thus, the carry in to a particular bit may be H or xe2x80x9ctruexe2x80x9d if the carry in to the block is 0, which is represented by C0H. Similarly the carry in to a particular bit may be L or xe2x80x9cfalsexe2x80x9d if the carry in to the block is 0, C0L. Note that COH and C0L are complements of each other. Similar statements may be made for C1H and C1L. Therefore, the four signals represent the actual and the complement of the signals C0 and C1, with H being the true or actual, and L being the false or complement.
Each of the four signals are required for processing of the carrys, because logical circuits within the system, such as exclusive OR, use both true and complements of input signals. Each of these signals must be generated, and transmitted through the system, and then routed to appropriate destinations. This is costly in terms of chip complexity, and chip area used.
Therefore, there is a need in the art for a carry select adder that requires fewer signals to be generated and transmitted through the system.
These and other objects, features and technical advantages are achieved by a system and method which has a reduced number of encoded signals to represent the conditional carry bit.
In considering the operation of a carry chain, it is apparent that not all possible combinations of C0H, C0L and C1H, C1L need to be generated. For example, C0H always implies C1H, in other words if carry in to a bit is true for block carry in of zero, then carry in to this bit will certainly be true for block carry in of one. If C0H is true, then the carry into the bit is generated within the block, and thus, would not be affected by the addition of 1 from a block carry in of 1. Thus, C1H does not have to be calculated for this bit. Similarly, C1L always implies C0L, in other words if carry in to a bit is false for block carry in of one, then carry in to the bit will certainly be false for block carry in of zero. If C1L is true, then the carry into the block is lost within the block, and thus, the carry in to the bit would not be affected by the subtraction of 1 from a block carry in of 0. Thus, C0L does not have to be calculated for this bit. Note that with the complement pairs, i.e. C0H and C0L and C1H and C1L, only one of each pair will be true at any given time.
Therefore, a more compact encoding of the C0/C1 bits is possible. In keeping with the PKG naming convention (Propagate, Kill, Generate) of encoding the adder inputs, one-of-three encoding can be used to represent the conditional carry into a bit. Only one of the signals would be high at any time, the other two would be low. The three signals are Gin, Kin, and Pin. The Gin signal is true where a bit has a carry in of one regardless of carry in to the block, i.e. the carry in to the bit is generated within the block. The Kin signal is true where a carry in to a bit is zero regardless of the carry in to the block, i.e. any carry in to the block is killed before it gets to the bit. The Pin signal is true where a bit has a carry in that is the same as the carry in to the block, i.e. the carry in to the block is propagated up to the bit. These signals are used in the calculation of the sum bits, i.e. the actual bits of the bit streams being added together.
Since only three signals are generated, the number of field-effect transistors (FETs) required to implement the adder are reduced. Moreover, since only three signals are being transmitted, the amount of routing mechanisms, e.g. wire, is also reduced. Thus, the complexity and surface area of the adder are reduced.
Therefore, it is a technical advantage of one aspect of the present invention to have one-of-three encoding to represent the conditional carry into each bit of a block of bits. It is a further technical advantage of one aspect of the present invention to represent the signals as propagate, kill, or generate, based upon the carry in to the block.
It is still a further technical advantage of one aspect of the present invention to provide a system and method which has a reduced number of encoded signals to represent a conditional carry bit in addition operations. Accordingly, it is a technical advantage of one aspect of the present invention to reduce chip complexity (i.e., circuitry complexity) required for performing addition operations. Also, it is a technical advantage of one aspect of the present invention to reduce the chip area required for performing addition operations.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.